package com.test22.fastsort;

import java.util.Arrays;

public class FastSortDemo {
	public static void main(String[] args) {
		int[] arr = {2,0,1,3};
		new FastSortDemo().fastSort(arr);
		System.out.println(Arrays.toString(arr));
	}

	private void fastSort(int[] arr) {
		this.traverse(arr, 0, arr.length-1);
	}
	private void traverse(int[] arr,int start,int end){
		if (start>=end) {
			return;
		}
		
		//定义本次比较的指针
		int mid = arr[end];
		int left = start;
		int right = end-1;
		//判断mid是不是已经找到自己位置了
		while (left < right) {
			//先循环左边，只要左边还小，而且指针没有超过右边。就一直循环，知道找到一个比mid大的
			while (arr[left] <= mid && left < right) {
				left++;
			}
			while (arr[right] >= mid && left < right) {
				right--;
			}
			swap(arr, left, right);
		}
		
		if (arr[left]>=mid) {
			swap(arr, left, end);
		}else{
			left++;
		}
		
		this.traverse(arr, start, left-1);
		this.traverse(arr, left+1, end);
	}
	
	private void swap(int[] arr,int i,int j){
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}
